import java.util.*;

public class MaxElegance {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取n和k
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // 读取每个项目的profit和category
        int[][] items = new int[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = scanner.nextInt();  // profit
            items[i][1] = scanner.nextInt();  // category
        }

        // 按照利润从大到小排序
        Arrays.sort(items, (a, b) -> b[0] - a[0]);

        // 使用优先队列（小根堆）来保持当前选择的k个项目中最小的利润
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 哈希集合用于记录已选择的不同类别
        Set<Integer> selectedCategories = new HashSet<>();

        long totalProfit = 0;
        long maxElegance = 0;

        // 遍历前k个项目
        for (int i = 0; i < k; i++) {
            totalProfit += items[i][0];
            minHeap.offer(items[i][0]);
            selectedCategories.add(items[i][1]);
        }

        // 初始优雅度计算
        maxElegance = totalProfit + (long) selectedCategories.size() * selectedCategories.size();

        // 从k之后的项目开始，尝试替换已有项目以获得更高优雅度
        for (int i = k; i < n; i++) {
            if (!selectedCategories.contains(items[i][1])) {
                // 如果找到一个新的类别，尝试替换掉最小利润的项目
                totalProfit -= minHeap.poll();
                totalProfit += items[i][0];
                selectedCategories.add(items[i][1]);
                minHeap.offer(items[i][0]);

                // 重新计算优雅度
                long currentElegance = totalProfit + (long) selectedCategories.size() * selectedCategories.size();
                maxElegance = Math.max(maxElegance, currentElegance);
            }
        }

        // 输出最大优雅度
        System.out.println(maxElegance);
    }
}
